Store-and-forward devices, such as switches and routers, are used in packet networks, such as the Internet, for directing traffic at interconnection points. The store-and-forward devices include a plurality of line cards for receiving and transmitting data from/to external sources. The line cards are connected to one another via a backplane and a switching fabric. The backplane provides data paths between line cards and the switching fabric and the switching fabric provides configurable data paths between line cards. The line cards receiving data from external sources (ingress ports) receive data (packets) of various sizes. The data received are stored in queues prior to being transmitted to the appropriate line cards for transmission to external sources (egress ports). The packets include a header that identifies the destination of the packet. The packet is stored in the queue associated with that destination. The packet may also identify a priority for the data and the ingress port may also include queues for the various priorities.
The ingress ports send requests for transmitting data to a scheduler within the switching fabric. The scheduler generates grants for the queues that should transmit packets therefrom. The packets are switched through a crossbar switching matrix in batches. A batch consists of at most one packet selected from each input port. Thus, no more than one of the packets is destined for each output port. The packets in a batch are transferred in parallel across the crossbar switching matrix. While the packets from a scheduled batch are being transferred through the crossbar, the scheduler can select the packets to form the next batch, so that the transmission of the new batch of packets can start as soon as transmission of the current batch ends. At the end of the batch of packets, the fabric scheduler re-configures the crossbar-switching matrix so as to connect input ports to output ports based on next packet destination. Because the packets are transferred in batches, the switching paths in the crossbar-switching matrix are kept unchanged for the duration of the longest packet being transferred across the crossbar in that batch. For example, when a 50-byte packet and a 1500-byte packet are part of the same batch, the crossbar is maintained in the same configuration for the duration of the 1500-byte packet, and only 1/30th of the bandwidth of the path is used by the 50-byte packet.
The variable-size packets may be divided into fixed-size units (segments) before switching through the crossbar switching fabric. The segments are combined into the original packet at the output of the fabric. The fabric scheduler selects at most one segment from each input port to form a batch, such that the destination port numbers associated with the cells in the same batch are distinct. The segment size is typically chosen to correspond to the size of the smallest packet switched by the fabric, plus the size of any internal headers added by the router or switch before passing the packet through the fabric. The fabric scheduler computes a new schedule for each batch of segments during the transmission time of the segments. In a high-speed switch, this time interval can be extremely short. For example, with a cell size of 64 bytes and a port rate of 10 Gigabits/second, the fabric scheduler schedules a new batch of cells every 51.2 nanoseconds. The crossbar switching matrix is also configured at intervals of 51.2 nanoseconds. As the port speed is increased, both the fabric scheduler and the crossbar reconfiguration are made correspondingly faster.
The requests from a particular ingress port inform the scheduler of the amount of data that was added to the queue since the last request was sent. That is, the ingress port does not indicate a total amount of data in a corresponding queue. The scheduler maintains a count of the data within the queues. That is, the scheduler adds the data from the requests and subtracts the data that is granted (and eventually de-queued and transmitted) from that queue. For example, if a first request indicated 3 segments were in the queue, two segments have subsequently been granted, and a new request includes 1 segment was queued since the last request, the scheduler will know that the queue contains 2 segments (3 segments in 1st request−2 segments granted+1 segment in 2nd request). As each request only accounts for data received since the last request, the loss of a request or grant will result in an inconsistent state. If a request is lost, the scheduler will not know that the data identified in the request is part of the queue. If a grant is lost and the ingress port accordingly does not de-queue the data, the scheduler will exclude the data contained in the grant from the count even though the data will not be de-queued or transmitted due to the lost grant.